package com.alex.algorithm.easy;

import java.util.Stack;

/**
 * 校验括号
 */
public class ValidateParenthenes {

    private static char[] LEFT_CHARS = {'(','[','{'};
    private static char[] RIGHT_CHAR = {')',']','}'};

    public static void main(String[] args) {
        System.out.println(isValid("{}[]()"));
        System.out.println(isValid("{}[()"));
        System.out.println(isValid("{}[()]"));
    }

    private static boolean isValid(String str) {
        if (str == null || str.length() == 0){
            return false;
        }
        Stack<Character> charStack = new Stack<>();
        char[] chars = str.toCharArray();
        for (int i = 0; i < chars.length; ++i)  {
            int leftIndex = indexOfChar(LEFT_CHARS, chars[i]);
            if (leftIndex != -1) {
                charStack.push(chars[i]);
            }else {
                if (charStack.isEmpty()){
                    return false;
                }
                Character topChar = charStack.pop();
                if (topChar == null || (indexOfChar(LEFT_CHARS, topChar) != indexOfChar(RIGHT_CHAR, chars[i]))){
                   return false;
                }
            }
        }
        if (!charStack.isEmpty()){
            return false;
        }
        return true;
    }

    private static int indexOfChar(char[] chars, char c) {
        for (int i = 0; i < chars.length; ++i) {
            if (chars[i] == c) {
                return i;
            }
        }
        return -1;
    }
}
